//
// Created by liaoh on 2021/8/2.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void CountSort(vector<int> &data, vector<int> &result) {
    // 空数据返回
    if (data.size() < 1) return;

    // 找出最大最小值
    int min = 100;
    int max = 0;
    for (int i = 0; i < data.size(); ++i) {
        if (max < data[i]) max = data[i];
        else if (min > data[i]) min = data[i];
    }
    cout << "min = " << min << endl;
    cout << "max = " << max << endl;
    // 创建计数容器
    int count = max - min + 1;
    vector<int> box(count, 0);
    // 开始计数
    for (int i = 0; i < data.size(); ++i) {
        int value = data[i] - min;
        box[value]++;
    }
    for (int i = 0; i < box.size(); ++i) {
        cout << "box i = " << i << " count = " << box[i] << endl;
    }
    // 把结果返回给result数组
    int index = 0;
    int rIndex = 0;
    while (index < box.size()) {
        if (box[index] > 0) {
            result[rIndex] = index + min;
            box[index]--;
            rIndex++;
        } else index++;
    }
    for (int i = 0; i < result.size(); ++i) {
        cout << "result i = " << i << " value = " << result[i] << endl;
    }
}

int main() {
//    vector<int> data = {0, 5, 7, 9, 6, 3, 4, 5, 2, 8, 6, 9, 2, 1};
    vector<int> data = {2,2,8,5,3,6,4,4,5,6,7,9,8,6,5,4,8,5,4,5,8,6,6};
    vector<int> result(data.size(), 0);

    CountSort(data, result);

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

